class UnificationError(Exception):
    pass

class IncompatibleTypeError(UnificationError):
    def __init__(self, a, b):
        self.a = a
        self.b = b

    def __str__(self):
        return '%s is incompatible with %s.' % (self.a, self.b)

class Unifier:
    def __init__(self):
        self.sets = []

    def __repr__(self):
        return 'Unifier(%s)' % repr(self.sets)
        
    def find(self, a):
        for i in range(len(self.sets)):
            for j in range(len(self.sets[i])):
                if a in self.sets[i][j]:
                    return i, j
        raise ValueError
        
    def add_subs(self, a, b):
        try:
            ai, aj = self.find(a)
            try:
                bi, bj = self.find(b)
                if bi == ai:
                    return
                elif bj == 0:
                    self.sets[ai][1].update(self.sets[bi][0])
                    self.sets[ai][1].update(self.sets[bi][1])
                    del self.sets[bi]
                    return
                else:
                    self.sets[ai][0].update(self.sets[bi][0])
                    self.sets[ai][1].update(self.sets[bi][1])
                    del self.sets[bi]
                    return
            except ValueError:
                self.sets[ai][1].add(b)
                return
        except ValueError:
            try:
                bi, bj = self.find(b)
                if bj == 0:
                    self.sets[bi][1].update(self.sets[bi][0])
                    self.sets[bi][0] = set([a])
                    return
                else:
                    self.sets[bi][0].add(a)
                    return
            except ValueError:
                self.sets.append((set([a]), set([b])))
                return

    def unified_subs(self):
        result = {}
        for i in range(len(self.sets)):
            unified = list(self.sets[i][1])
            value = unified.pop()
            while unified:
                value = value.unify(unified.pop())

            for key in self.sets[i][0]:
                if key in value.variables and key != value:
                    raise UnificationError('Recursive types not allowed.')

                result[key] = value

        return result
    
    def apply(self, other):
        subs = self.unified_subs()
        for key, value in subs.iteritems():
            other = other.substitute(value, key)
        return other
